import collections


class Solution(object):
    def areSentencesSimilar(self, sentence1, sentence2, similarPairs):
        """
        :type sentence1: List[str]
        :type sentence2: List[str]
        :type similarPairs: List[List[str]]
        :rtype: bool
        """
        if len(sentence1) != len(sentence2):
            return False
        n = len(sentence1)
        d = collections.defaultdict(set)
        for pair in similarPairs:
            d[pair[0]].add(pair[1])
            d[pair[1]].add(pair[0])
        for i in range(n):
            if sentence1[i] != sentence2[i]:
                if sentence1[i] not in d:
                    return False
                else:
                    if sentence2[i] not in d[sentence1[i]]:
                        return False
        return True


data = Solution()
sentence1 = ["great", "acting", "skills"]
sentence2 = ["fine", "drama", "talent"]
similarPairs = [["great", "fine"], ["drama", "acting"], ["skills", "talent"]]
print(data.areSentencesSimilar(sentence1, sentence2, similarPairs))
sentence1 = ["one", "excellent", "meal"]
sentence2 = ["one", "good", "dinner"]
similarPairs = [["great", "good"], ["extraordinary", "good"], ["well", "good"], ["wonderful", "good"], ["excellent", "good"],
 ["fine", "good"], ["nice", "good"], ["any", "one"], ["some", "one"], ["unique", "one"], ["the", "one"], ["an", "one"],
 ["single", "one"], ["a", "one"], ["truck", "car"], ["wagon", "car"], ["automobile", "car"], ["auto", "car"],
 ["vehicle", "car"], ["entertain", "have"], ["drink", "have"], ["eat", "have"], ["take", "have"], ["fruits", "meal"],
 ["brunch", "meal"], ["breakfast", "meal"], ["food", "meal"], ["dinner", "meal"], ["super", "meal"], ["lunch", "meal"],
 ["possess", "own"], ["keep", "own"], ["have", "own"], ["extremely", "very"], ["actually", "very"], ["really", "very"],
 ["super", "very"]]
print(data.areSentencesSimilar(sentence1, sentence2, similarPairs))